InforLorV4, Main, Exploration, bibRecord, 006557

A note on maximally repeated sub-patterns of a point set

Identifieur interne : 006557 ( Main/Exploration ); précédent : 006556; suivant : 006558

A note on maximally repeated sub-patterns of a point set

Auteurs : Véronique Cortier [France] ; Xavier Goaoc [France] ; Mira Lee [Corée du Sud] ; Hyeon-Suk Na [Corée du Sud]

Source :

RBID : Hal:inria-00070247

English descriptors

mix :
- discrete geometry, point sets, repeated configurations.

Abstract

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is in fact $\Theta(2^n/2)$ in the worst case, regardless of the dimension $d$.

Url:

https://hal.inria.fr/inria-00070247

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000802
to stream Hal, to step Curation: 000802
to stream Hal, to step Checkpoint: 004998
to stream Main, to step Merge: 006888
to stream Main, to step Curation: 006557

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">A note on maximally repeated sub-patterns of a point set</title>
<author><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2366" status="OLD"><idno type="RNSR">200318302K</idno>
<orgName>Combination of approaches to the security of infinite states systems</orgName>
<orgName type="acronym">CASSIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/cassis</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-866" type="direct"></relation>
<relation active="#struct-242365" type="indirect"></relation>
<relation active="#struct-300261" type="indirect"></relation>
<relation active="#struct-300360" type="indirect"></relation>
<relation name="UMR6174" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno>
<idno type="RNSR">200412232H</idno>
<orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName>
<orgName type="acronym">FEMTO-ST</orgName>
<desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.femto-st.fr</ref>
</desc>
<listRelation><relation active="#struct-242365" type="direct"></relation>
<relation active="#struct-300261" type="direct"></relation>
<relation active="#struct-300360" type="direct"></relation>
<relation name="UMR6174" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno>
<idno type="ISNI">0000 0001 2188 3779 </idno>
<orgName>Université de Franche-Comté</orgName>
<orgName type="acronym">UFC</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.univ-fcomte.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName>
<orgName type="acronym">UTBM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName>
<orgName type="acronym">ENSMM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city" wicri:auto="siege">Besançon</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de Franche-Comté</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName>
<placeName><settlement type="city" wicri:auto="siege">Belfort</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de technologie de Belfort-Montbéliard</orgName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<orgName type="acronym">KAIST</orgName>
<desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://www.kaist.edu/edu.html</ref>
</desc>
<listRelation><relation active="#struct-365285" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName>
<desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://com_e.ssu.ac.kr/</ref>
</desc>
<listRelation><relation active="#struct-300888" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00070247</idno>
<idno type="halId">inria-00070247</idno>
<idno type="halUri">https://hal.inria.fr/inria-00070247</idno>
<idno type="url">https://hal.inria.fr/inria-00070247</idno>
<date when="2005">2005</date>
<idno type="wicri:Area/Hal/Corpus">000802</idno>
<idno type="wicri:Area/Hal/Curation">000802</idno>
<idno type="wicri:Area/Hal/Checkpoint">004998</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">004998</idno>
<idno type="wicri:Area/Main/Merge">006888</idno>
<idno type="wicri:Area/Main/Curation">006557</idno>
<idno type="wicri:Area/Main/Exploration">006557</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">A note on maximally repeated sub-patterns of a point set</title>
<author><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2366" status="OLD"><idno type="RNSR">200318302K</idno>
<orgName>Combination of approaches to the security of infinite states systems</orgName>
<orgName type="acronym">CASSIS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/cassis</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-866" type="direct"></relation>
<relation active="#struct-242365" type="indirect"></relation>
<relation active="#struct-300261" type="indirect"></relation>
<relation active="#struct-300360" type="indirect"></relation>
<relation name="UMR6174" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno>
<idno type="RNSR">200412232H</idno>
<orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName>
<orgName type="acronym">FEMTO-ST</orgName>
<desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.femto-st.fr</ref>
</desc>
<listRelation><relation active="#struct-242365" type="direct"></relation>
<relation active="#struct-300261" type="direct"></relation>
<relation active="#struct-300360" type="direct"></relation>
<relation name="UMR6174" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno>
<idno type="ISNI">0000 0001 2188 3779 </idno>
<orgName>Université de Franche-Comté</orgName>
<orgName type="acronym">UFC</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.univ-fcomte.fr</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName>
<orgName type="acronym">UTBM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName>
<orgName type="acronym">ENSMM</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city" wicri:auto="siege">Besançon</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de Franche-Comté</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName>
<placeName><settlement type="city" wicri:auto="siege">Belfort</settlement>
<region type="region" nuts="2">Franche-Comté</region>
</placeName>
<orgName type="university">Université de technologie de Belfort-Montbéliard</orgName>
</affiliation>
</author>
<author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName>
<orgName type="acronym">KAIST</orgName>
<desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://www.kaist.edu/edu.html</ref>
</desc>
<listRelation><relation active="#struct-365285" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
<author><name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7891" status="VALID"><orgName>School of Computing - Soongsil University, Séoul</orgName>
<desc><address><addrLine>Room #105, Information Science Building - Soongsil University, 511 - Sangdo-dong, Dongjak-gu - Seoul 156-743 - Korea</addrLine>
<country key="KR"></country>
</address>
<ref type="url">http://com_e.ssu.ac.kr/</ref>
</desc>
<listRelation><relation active="#struct-300888" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300888" type="direct"><org type="institution" xml:id="struct-300888" status="VALID"><orgName>Soongsil University, Seoul</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Corée du Sud</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>discrete geometry</term>
<term>point sets</term>
<term>repeated configurations</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is in fact $\Theta(2^n/2)$ in the worst case, regardless of the dimension $d$.</div>
</front>
</TEI>
<affiliations><list><country><li>Corée du Sud</li>
<li>France</li>
</country>
<region><li>Franche-Comté</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Belfort</li>
<li>Besançon</li>
<li>Nancy</li>
</settlement>
<orgName><li>Institut national polytechnique de Lorraine</li>
<li>Université Nancy 2</li>
<li>Université de Bourgogne Franche-Comté</li>
<li>Université de Franche-Comté</li>
<li>Université de Lorraine</li>
<li>Université de technologie de Belfort-Montbéliard</li>
</orgName>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Cortier, Veronique" sort="Cortier, Veronique" uniqKey="Cortier V" first="Véronique" last="Cortier">Véronique Cortier</name>
</region>
<name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name>
</country>
<country name="Corée du Sud"><noRegion><name sortKey="Lee, Mira" sort="Lee, Mira" uniqKey="Lee M" first="Mira" last="Lee">Mira Lee</name>
</noRegion>
<name sortKey="Na, Hyeon Suk" sort="Na, Hyeon Suk" uniqKey="Na H" first="Hyeon-Suk" last="Na">Hyeon-Suk Na</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006557 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006557 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:inria-00070247
   |texte=   A note on maximally repeated sub-patterns of a point set
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

A note on maximally repeated sub-patterns of a point set

A note on maximally repeated sub-patterns of a point set

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri